Essentials of Compilation
Essentials of Compilationは小さなコンパイラから徐々に拡張していきながら実装技術を学ぶ本。RacketでRacketのサブセットを実装するバージョンとPythonでPythonのサブセットを実装するバージョンがある。
LaTeXで書かれた両バージョンの原稿、Racket版を採用している大学のコース資料、Python版を採用している大学のコース資料がウェブで公開されている。
目次
Preliminaries
本書を通して登場するASTやパターンマッチ、再帰などの技法を紹介し、小さなインタプリタを作成する。
Integers and Variables
整数型の値、加減算、符号反転、括弧、変数束縛を含む小さな言語をx86-64アセンブリ言語にコンパイルする。
Parsing（Python版のみ）
パーサージェネレーターLarkを使った字句解析と構文解析を行う。
Larkに実装されている構文解析アルゴリズムのうち、Earley法とLALR法のふたつを解説する。
Register Allocation
グラフ彩色アルゴリズムによるレジスタ割り当てや生存区間解析に取り組む。
Booleans and Conditionals
自作言語に真偽値や比較演算、条件分岐を組み込む。
Loops and Dataflow Analysis
自作言語にループ構文を組み込み、データフロー解析を発展させる。
Tuples and Garbage Collection
自作言語にタプルとGCを導入する。
Functions
自作言語に関数を導入する。
Lexically Scoped Functions
自作言語の関数にクロージャを実装する。
Dynamic Typing
ここまでの自作言語は項の型が静的に決まるようになっていた。ここでは値に型タグをつける方式に切り替え、Any型を導入する。
Gradual Typing
前章の実装をさらに発展させて、自作言語に漸進的型付けを実装する。
Generics
自作言語にジェネリクス（パラメトリック多相）を追加する。
Appendix
トピック（コース資料より抜粋）
命令選択
レジスタ割り当て
静的型検査
条件制御フロー
変更可能なデータ
ガベージコレクション
手続きと呼び出し規約
第一級の関数とクロージャ変換
動的型付け
ジェネリクス（パラメトリック多相）
高水準最適化（インライン化、定数の畳み込み、コピー伝播など）
#本